package _array

import org.junit.Assert
import org.junit.Test

/**
 * https://programmercarl.com/0027.%E7%A7%BB%E9%99%A4%E5%85%83%E7%B4%A0.html
 * https://leetcode.cn/problems/remove-element/description/
 *
 * 移除元素
 * 数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。
 */

/**
 * 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
 *
 * 输入：nums = [3,2,2,3], val = 3
 * 输出：2, nums = [2,2,_,_]
 *
 * 输入：nums = [0,1,2,2,3,0,4,2], val = 2
 * 输出：5, nums = [0,1,4,0,3,_,_,_]
 */
class Test6 {
    // T = N
    // S = N
    // fun removeElement(nums: IntArray, `val`: Int): Int {
    //     val tArray: IntArray = IntArray(nums.size)
    //     var count = 0
    //     for (i in 0..nums.size - 1) {
    //         if (nums[i] != `val`) {
    //             tArray[count] = nums[i]
    //             count++
    //         }
    //     }
    //     for (i in 0..count - 1) {
    //         nums[i] = tArray[i]
    //     }

    //     return count
    // }


    // T - N
    // S - 1
    fun removeElement(nums: IntArray, `val`: Int): Int {
        /*
         * left = 0
         * right = 0
         * for(right -> end){
         *   if(right == v){
         *   }
         *   else{
         *      swipe right left if not same
         *      left++
         *  }
            right ++
         * }
         */
        var left = 0
        for (right in 0..nums.size - 1) { // 0,1,2,2,3,0,4,2
            if (nums[right] != `val`) {
                if (nums[left] != nums[right]) {
                    // swipe
//                val t1 = nums[left]
//                val t2 = nums[right]
//                nums[left] = t2
//                nums[right] = t1
                    val t1 = nums[left]
                    nums[left] = nums[right]
                    nums[right] = t1
                }
                left += 1
            }
        }
        return left
    }

    @Test
    fun test_1() {
        /**
         *  输入：nums = [3,2,2,3], val = 3
         *  输出：2, nums = [2,2,_,_]
         */
        val array = intArrayOf(3, 2, 2, 3)
        val actual = removeElement(array, 3)
        val expect = 2
        Assert.assertEquals(expect, actual)
    }

    @Test
    fun test_2() {
        /**
         * 输入：nums = [0,1,2,2,3,0,4,2], val = 2
         *  输出：5, nums = [0,1,4,0,3,_,_,_]
         */
        val array = intArrayOf(0, 1, 2, 2, 3, 0, 4, 2, 2)
        val actual = removeElement(array, 2)
        val expect = 5
        Assert.assertEquals(expect, actual)
    }
}